package LeetCode.month01.day17;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class No295 {
    public static void main(String[] args) {
        MedianFinder m = new MedianFinder();
        m.addNum(-1);
        System.out.println(m.findMedian());
        m.addNum(-2);
        System.out.println(m.findMedian());
        m.addNum(-3);
        System.out.println(m.findMedian());
        m.addNum(-4);
        System.out.println(m.findMedian());
        m.addNum(-5);
        System.out.println(m.findMedian());

    }
}

class MedianFinder {
    PriorityQueue<Integer> minqueue;
    PriorityQueue<Integer> maxqueue;

    public MedianFinder() {
        minqueue = new PriorityQueue<Integer>();
        maxqueue = new PriorityQueue<Integer>((x,y)->y-x);
    }

    public void addNum(int num) {
        if(minqueue.isEmpty()||num>minqueue.peek()){
            minqueue.offer(num);
        }else{
            maxqueue.offer(num);
        }
        if(minqueue.size()>maxqueue.size()+1){
            maxqueue.offer(minqueue.poll());
        }else if(maxqueue.size()>minqueue.size()){
            minqueue.offer(maxqueue.poll());
        }
    }

    public double findMedian() {
        if(minqueue.size()==maxqueue.size()) {
            return (minqueue.peek()+maxqueue.peek())/2.0;
        } else {
            return minqueue.peek();
        }
    }
}